//
// Description: 5965. 相同元素的间隔之和
// Created by Loading on 2021/12/26.
//

#include <bits/stdc++.h>

using namespace std;

vector<long long> getDistances(vector<int> &arr) {
    // 记录每个元素出现的下标
    unordered_map<int, vector<int>> m;
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
        m[arr[i]].emplace_back(i);
    }

    // 前缀和与后缀和
    unordered_map<int, vector<long long>> m_begin, m_end;
    for (auto it : m) {
        int size = it.second.size();
        m_begin[it.first].resize(size);
        // 计算当前元素到其左侧所有相同元素的距离和
        for (int i = 1; i < size; ++i) {
            m_begin[it.first][i] = m_begin[it.first][i - 1] + i * (it.second[i] - it.second[i - 1]);
        }
    }
    for (auto it : m) {
        int size = it.second.size();
        m_end[it.first].resize(size);
        // 计算当前元素到其右侧所有相同元素的距离和
        for (int i = size - 2; i >= 0; --i) {
            m_end[it.first][i] = m_end[it.first][i + 1] + (size - i - 1) * (it.second[i + 1] - it.second[i]);
        }
    }

    // 记录每个数字计算到第几个了
    vector<int> index(1e5 + 10);
    vector<long long> res;
    for (auto x : arr) {
        res.emplace_back(m_begin[x][index[x]] + m_end[x][index[x]]);
        ++index[x];
    }

    return res;
}

int main() {
    vector<int> arr = {10, 5, 10, 10};
    vector<long long> res = getDistances(arr);
    for (auto x : res) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}